/*
**********************************************************
*
* Programme :	libgraphe.c
*
* ecrit par :	Najim Boujedli et Jeremy Paneri
*
* resume :		création et manipulation d'une structure de graphe
* 
*
*
* date : 		24/02/13
*
***********************************************************
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "libgraphe.h"


/*
 * Fonction :		creerGraphe
 *
 * Parametres :		nbSommet, le nombre de sommets maximum possible pour le graphe
 *
 * Retour :			TypGraphe*, un pointeur sur le graphe créé
 *
 * Description :	créé un graphe constitué de nbSommet listes vides
 *
 */
TypGraphe* creerGraphe(int nbSommet) {
	TypGraphe* graphe;
	graphe = (TypGraphe*) malloc(sizeof(TypGraphe));

	graphe->nbMaxSommets = nbSommet + 1;
	graphe->listesAdjacences = (TypVoisins**) malloc(sizeof(TypVoisins*)*(graphe->nbMaxSommets));

	int i;
	for (i = 1; i < graphe->nbMaxSommets; ++i)
	{
		graphe->listesAdjacences[i] = NULL;
	}

	return graphe;
}


/*
 * Fonction :		supprimerGraphe
 *
 * Parametres :		TypGraphe* graphe, le graphe à supprimer
 *
 * Retour :			rien
 *
 * Description :	libère l'intégralité du graphe
 *
 */
void supprimerGraphe(TypGraphe** graphe) {
	int i, j;

	for (i = 1; i < (*graphe)->nbMaxSommets; ++i) {
		for (j = 1; j < (*graphe)->nbMaxSommets; ++j) {
			supprimerVoisin((*graphe)->listesAdjacences[i], j);
		}
		free((*graphe)->listesAdjacences[i]);
		(*graphe)->listesAdjacences[i] = NULL;
	}

	free((*graphe)->listesAdjacences);
	(*graphe)->listesAdjacences = NULL;

	free(*graphe);
	*graphe = NULL; 
}


/*
 * Fonction :		sortieGraphe
 *
 * Parametres :		TypGraphe* graphe, le graphe à afficher
 *					char* flux, où le graphe doit sortir (ex: stdout)
 *
 * Retour :			0	sortie effectuée
 *					1	graphe vide
 *					2	erreur de flux
 *
 * Description :	affiche dans la console une représentation du graphe
 *
 */
int sortieGraphe(char* flux, TypGraphe* graphe)
{
	if(graphe == NULL)
	{
		return 1;
	}

	FILE* output;


	// Détermination du flux de sortie
	if(flux == NULL)
	{
		output = stdout;
	}
	else
	{
		// Ouverture du fichier
		output = fopen(flux, "w+");
		if(output == NULL)
		{
			return 2;
		}
	}
	

	// Affichage
	fprintf(output, "# nombre maximum de sommets\n%d\n", graphe->nbMaxSommets-1);

	fprintf(output, "# sommets : voisins\n");

	int i;
	for (i = 1; i < graphe->nbMaxSommets; ++i)
	{
		if(graphe->listesAdjacences[i] != NULL) {
			fprintf(output, "%d : ", i);
			sortieListe(output, graphe->listesAdjacences[i]);
		}
	}


	// On ferme le descripteur du fichier
	if(output != stdout)
	{
		fclose(output);
	}

	return 0;
}


/*
 * Fonction :		lectureGraphe
 *
 * Parametres :		char* fichier, le chemin du fichier de sauvegarde du graphe
 *
 * Retour :			TypGraphe*, le graphe créé
 *					NULL, en cas d'erreur
 *
 * Description :	créé et renvoie un graphe correspondant au contenu d'un fichier de sauvegarde de graphe
 *
 */
TypGraphe* lectureGraphe(char* fichier)
{
	// Ouverture du fichier
	FILE* input = fopen(fichier, "r");
	if(input == NULL)
	{
		return NULL;
	}

	// Variables servant à la lecture des éléments du fichier
	char* member = NULL;
	char* line = NULL;
	size_t size = 0;
	ssize_t read;

	TypGraphe* graphe;
	int tMaxG;
	double poids;
	int sommet, voisin;

	// La lecture doit se faire en deux passes :
	// - la première permet de créer le graphe et les sommets,
	// - la deuxième permet de créer les arêtes.


	/* PREMIÈRE PASSE */

	// La première ligne est un commentaire : on l'ignore
	if(!getline(&line, &size, input)){
		printf("erreur\n");
	}

	// La deuxième contient le nombre maximum de sommets
	if(!getline(&line, &size, input)){
		printf("erreur\n");
	}
	sscanf(line, "%d", &tMaxG);
	graphe = creerGraphe(tMaxG);

	// La troisième est un commentaire : on l'ignore également
	if(!getline(&line, &size, input)){
		printf("erreur\n");
	}


	// On récupère le numéro du sommet de chaque ligne pour le créer
	while((read = getline(&line, &size, input)) != -1)
	{
		sscanf(line, "%d : %*s", &sommet);
		insertionSommet(graphe, sommet);
	}

	rewind(input);


	/* DEUXIÈME PASSE */

	// On ignore les trois premières lignes
	if(!getline(&line, &size, input)){
		printf("erreur\n");
	}
	if(!getline(&line, &size, input)){
		printf("erreur\n");
	}
	if(!getline(&line, &size, input)){
		printf("erreur\n");
	}

	free(line);
	line = NULL;

	// Pour chaque ligne (= chaque sommet)
	while((read = getline(&line, &size, input)) != -1)
	{
		// On récupère le sommet de départ et on ignore l'arête -1
		sscanf(line, "%d : %*s", &sommet);
		strsep(&line, ",");

		// Pour chaque membre séparé par une virgule (= chaque arête)
		while((member = strsep(&line, ",")) != NULL)
		{
			sscanf(member, " (%d/%lf)", &voisin, &poids);
			insertionAreteOriente(graphe, sommet, voisin, poids);
		}

		free(line);
		line = NULL;
	}

	free(line);
	line = NULL;


	fclose(input);

	return graphe;
}


/*
 * Fonction :		insertionSommet
 *
 * Parametres :		TypGraphe* graphe, le graphe à modifier
 *					int sommet, le sommet à ajouter au graphe
 *
 * Retour :			0	sommet ajouté
 *					1	sommet invalide
 *					2	sommet déjà existant
 *
 * Description :	ajoute un sommet au graphe
 *
 */
int insertionSommet(TypGraphe* graphe, int sommet) {

	// Sommet invalide
	if(sommet<1 || sommet>graphe->nbMaxSommets) {
		return 1;
	}

	// Le sommet existe déjà
	if(graphe->listesAdjacences[sommet] != NULL) {
		return 2;
	}

	graphe->listesAdjacences[sommet] = creerListe();
	return 0;
}


/*
 * Fonction :		insertionAreteOriente
 *
 * Parametres :		TypGraphe* graphe, le graphe à modifier
 *					int depart, le sommet de départ de l'arête
 *					int arrivee, le sommet d'arrivée de l'arête
 *					int poids, le poids de l'arête à ajouter
 *
 * Retour :			0 	si l'ajout s'est effectué correctement, 
 *					-1  si le sommet existe déjà
 *					2	ajout impossible
 *
 * Description :	ajoute une arête orientée au graphe
 *
 */
int insertionAreteOriente(TypGraphe* graphe, int depart, int arrivee, double poids) {

	if(	depart<1 || depart>graphe->nbMaxSommets
		|| arrivee<1 || arrivee>graphe->nbMaxSommets
		|| graphe->listesAdjacences[depart] == NULL) {
		return 2;
	}

	return ajouterVoisin(graphe->listesAdjacences[depart], arrivee, poids);
}


/*
 * Fonction :		insertionArete
 *
 * Parametres :		TypGraphe* graphe, le graphe à modifier
 *					int s1, le premier sommet
 *					int s2, le deuxième sommet
 *					double poids, le poids de l'arête à ajouter
 *
 * Retour :			0 	si l'ajout s'est effectué correctement, 
 *					-1  si l'arête existe déjà
 *					2	ajout impossible
 *
 * Description :	ajoute une arête au graphe
 *
 */
int insertionArete(TypGraphe* graphe, int s1, int s2, double poids) {

	if(	s1<1 || s1>graphe->nbMaxSommets
		|| s2<1 || s2>graphe->nbMaxSommets
		|| graphe->listesAdjacences[s1] == NULL
		|| graphe->listesAdjacences[s2] == NULL) {
		return 2;
	}

	int res1 = ajouterVoisin(graphe->listesAdjacences[s1], s2, poids);
	int res2 = ajouterVoisin(graphe->listesAdjacences[s2], s1, poids);

	if(res1==-1 || res2==-1)
	{
		return -1;
	}

	return 0;
}


/*
 * Fonction :		supprimeArete
 *
 * Parametres :		TypGraphe* graphe, le graphe à modifier
 *					int s1, le premier sommet
 *					int s2, le deuxième sommet
 *
 * Retour :			0 	si la suppression s'est effectuée correctement, 
 *					-1  si le sommet n'existe pas
 *					2	suppression impossible
 *
 * Description :	supprime une arête du graphe
 *
 */
int supprimeArete(TypGraphe* graphe, int s1, int s2) {

	if(	s1<1 || s1>graphe->nbMaxSommets
		|| s2<1 || s2>graphe->nbMaxSommets
		|| graphe->listesAdjacences[s1] == NULL
		|| graphe->listesAdjacences[s2] == NULL) {
		return 2;
	}

	int res1 = supprimerVoisin(graphe->listesAdjacences[s1], s2);
	int res2 = supprimerVoisin(graphe->listesAdjacences[s2], s1);

	if(res1==-1 || res2==-1)
	{
		return -1;
	}

	return 0;
}


/*
 * Fonction :		supprimeSommet
 *
 * Parametres :		TypGraphe* graphe, le graphe à modifier
 *					int s, le sommet à supprimer
 *
 * Retour :			0 	si la suppression s'est effectuée correctement, 
 *					-1  si le sommet n'existe pas
 *
 * Description :	supprime un sommet du graphe
 *
 */
int supprimeSommet(TypGraphe* graphe, int s) {

	if(	s<1 || s>graphe->nbMaxSommets || graphe->listesAdjacences[s] == NULL)
	{
		return -1;
	}

	int i;

	for (i = 1; i <= graphe->nbMaxSommets; i++)
	{
		supprimerVoisin(graphe->listesAdjacences[i], s);
	}

	free(graphe->listesAdjacences[s]);
	graphe->listesAdjacences[s] = NULL;

	return 0;
}


/*
 * Fonction :		supprimeAreteOriente
 *
 * Parametres :		TypGraphe* graphe, le graphe à modifier
 *					int depart, le sommet de départ de l'arête
 *					int arrivee, le sommet d'arrivée de l'arête
 *
 * Retour :			0 	si la suppression s'est effectuée correctement, 
 *					-1  si le sommet n'existe pas
 *					2	suppression impossible
 *
 * Description :	supprime orientée une arête du graphe
 *
 */
 int supprimeAreteOriente(TypGraphe* graphe, int depart, int arrivee) {

	if(	depart<1 || depart>graphe->nbMaxSommets
		|| arrivee<1 || arrivee>graphe->nbMaxSommets
		|| graphe->listesAdjacences[depart] == NULL) {
		return 2;
	}

	return supprimerVoisin(graphe->listesAdjacences[depart], arrivee);
}

double getPoidsArete(TypGraphe* graphe,int voisin1, int voisin2){

	return getPoidsSommet(graphe->listesAdjacences[voisin1], voisin2);
	
}




// Renvoie une arête TypArete d'un graphe complet
TypArete* getArete(TypGraphe* graphe, int voisin1, int voisin2) {
	double poids = getPoidsArete(graphe, voisin1, voisin2);

	// L'arrête n'existe pas
	if(poids == 0) {
		return NULL;
	}

	TypArete* arete = malloc(sizeof(TypArete));
	arete->v1 = voisin1;
	arete->v2 = voisin2;
	arete->poids = poids;
	return arete;
}




// Prend un graphe complet et renvoie un ARPM associé via l'algo de Prim.
TypGraphe* arpm(TypGraphe* graphe) {
	int nbSommets = graphe->nbMaxSommets-1;
	int i, j, k=0, l=1;

	// Création du graphe ARPM
	TypGraphe* arpm = creerGraphe(nbSommets);
	for(i=1 ; i<nbSommets+1 ; i++) {
		insertionSommet(arpm, i);
	}

	// Tableau des sommets présents dans le graphe
	int sommets[nbSommets];
	sommets[0] = 1;
	for(i=1 ; i<nbSommets ; i++) {
		sommets[i] = 0;
	}

	// Tas pour trier les arêtes
	Tas *prim = (Tas*) malloc(sizeof(Tas));
	prim->tailleTas = nbSommets*l-l*l;
	prim->tab = malloc(sizeof(TypArete*)*(prim->tailleTas));
	

	// Tant que tous les sommets ne sont pas dans le graphe
	while(l < nbSommets) {

		// On construit le tas
		for(i=1 ; i<=nbSommets ; i++) {
			if(sommets[i-1] == 1) {
				for(j=1 ; j<=nbSommets ; j++) {
					if(sommets[j-1] == 0) {
						prim->tab[k] = getArete(graphe, i, j);
						k++;
					}
				}
			}
		}

		// On ajoute la racine du tas trié au graphe
		faireTas(prim);
		sommets[prim->tab[0]->v2-1] = 1;
		insertionArete(arpm, prim->tab[0]->v1, prim->tab[0]->v2, prim->tab[0]->poids);

		// On réinitialise le tas
		for(i=0 ; i<k ; i++) {
			free(prim->tab[i]);
			prim->tab[i] = NULL;
		}
		k = 0;

		// On augmente la taille du tas pour le tour suivant
		l++;
		prim->tailleTas = nbSommets*l-l*l;
		prim->tab = realloc(prim->tab, sizeof(TypArete*)*(prim->tailleTas));
	}

	for(i=0 ; i<k ; i++) {
		free(prim->tab[i]);
		prim->tab[i] = NULL;
	}
	free(prim);
	prim = NULL;


	return arpm;
}
